   // 广度优先（层序遍历）
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(root == nullptr) return nullptr;
        if(1 == depth)  //创建一个新的 root，将原root 作为新root 的左孩子
            return new TreeNode(val, root, nullptr);

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            size_t size = q.size();
            --depth;      // 记录第几层
            for(size_t i = 0; i < size; ++i){
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left != nullptr)  q.push(cur->left);
                if(cur->right != nullptr) q.push(cur->right);
                if (depth == 1) {
                    cur->left = new TreeNode(val, cur->left, nullptr);
                    cur->right = new TreeNode(val, nullptr, cur->right);
                }
            }
            if(1 == depth) break;
        }
        return root;
    }